"""
给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/tencent/x53sd2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""



class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def __init__(self):
        pass

    """
    对于空节点，最大贡献值为 0
    对于叶子节点，最大贡献值即为节点值
    对于非叶子节点，最大贡献值为节点值加上它的孩子节点中最大贡献值
    参考：
    定义全局变量 ans
    函数 maxGain，计算一个节点的最大贡献值
    对于一个节点 node，以该节点为根节点的最大路径和为 node.val + left + right
    其中 left 和 right 为递归得到的左子树和右子树的最大路径和
    递归过程中更新全局变量 ans
    函数返回 node.val + max(left, right)，是向上一层递归返回该层最大贡献值
    """
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxsum = float('-inf')

        def dfs(r):
            if not r:
                return 0
            left = dfs(r.left)
            right = dfs(r.right)
            self.maxsum = max(self.maxsum, left + right + r.val)
            return max(0, max(left, right) + r.val)
        dfs(root)
        return self.maxsum
